<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="utf-8">
  

  
  <title>算法导论-第七章[快速排序] | 章军的博客</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="第七章 —- 快速排序">
<meta name="keywords" content="sort">
<meta property="og:type" content="article">
<meta property="og:title" content="算法导论-第七章[快速排序]">
<meta property="og:url" content="http://octopuscloud.top/2019/03/30/七章-快速排序/index.html">
<meta property="og:site_name" content="章军的博客">
<meta property="og:description" content="第七章 —- 快速排序">
<meta property="og:locale" content="China">
<meta property="og:updated_time" content="2019-09-11T04:27:11.572Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="算法导论-第七章[快速排序]">
<meta name="twitter:description" content="第七章 —- 快速排序">
  
    <link rel="alternate" href="/atom.xml" title="章军的博客" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link rel="stylesheet" href="/css/style.css">
</head>
</html>
<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">章军的博客</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://octopuscloud.top"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="ppost-七章-快速排序" class="article article-type-ppost" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2019/03/30/七章-快速排序/" class="article-date">
  <time datetime="2019-03-30T08:37:34.000Z" itemprop="datePublished">2019-03-30</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/categories/ReadNote/">ReadNote</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      算法导论-第七章[快速排序]
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1 id="第七章-—-快速排序"><a href="#第七章-—-快速排序" class="headerlink" title="第七章 —- 快速排序"></a>第七章 —- 快速排序</h1><a id="more"></a>
<h2 id="快速排序算法的算法描述"><a href="#快速排序算法的算法描述" class="headerlink" title="快速排序算法的算法描述"></a>快速排序算法的算法描述</h2><pre><code>快速排序的算法主要过程是在将原本数组分为两个子数组 ，递归调用。

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">QUICKSORT(A, start, end)</span><br><span class="line">	if start &lt; end</span><br><span class="line">		Q = PARTTION(A, start, end)</span><br><span class="line">		QUICKSORT(A, start, Q-1)</span><br><span class="line">		QUICKSORT(A, Q+1, end)</span><br><span class="line"></span><br><span class="line">PARTTION(A, p, r)</span><br><span class="line">	x ← A[r]</span><br><span class="line">	i ← p - 1</span><br><span class="line">	for j ← p to r-1</span><br><span class="line">		do if A[j] ≤ x</span><br><span class="line">			i += 1</span><br><span class="line">			swap(j,i)</span><br><span class="line">	swap(i+1, r)</span><br><span class="line"></span><br><span class="line">当数组 arry 经过 PARTTION 函数后 ，返回 Q 值。</span><br><span class="line">arry&#123;0,1,2,3.....n&#125;</span><br><span class="line">arry 经过 PARTTION 处理后 ，会返回一个 Q 值 。</span><br><span class="line">arry&#123;0,1,2..Q-1&#125; : 里面的值会小于 arry[Q] 。</span><br><span class="line">arry&#123;Q+1,...n&#125;: 里面的任意值都要答案与 arry[Q] 。</span><br><span class="line"></span><br><span class="line">RANDOM-PARTTION(A, start, end)</span><br><span class="line">	i ← RANDOM(start, end)</span><br><span class="line">	swap(i, end)</span><br><span class="line">	PARTTION(A, start, end)</span><br></pre></td></tr></table></figure>
</code></pre><h2 id="快速排序的性能"><a href="#快速排序的性能" class="headerlink" title="快速排序的性能"></a>快速排序的性能</h2><pre><code>主元素的选择会影响子数组的划分的对称性 ，而对称性会影响快速算法的性能 。如果每次子数组都能堆成的划分 ，快速算法性能会接近合并算法( Ѳ(nlg(n) )) 。划分子数组对称性极低 ，在性能上接近插入排序 (Ѳ(n^2)) 。
</code></pre><h3 id="最坏排序划分"><a href="#最坏排序划分" class="headerlink" title="最坏排序划分"></a>最坏排序划分</h3><pre><code>T(n) = T(n - q) + T(q) + cn
</code></pre><h3 id="最好排序划分"><a href="#最好排序划分" class="headerlink" title="最好排序划分"></a>最好排序划分</h3><h3 id="平衡的划分"><a href="#平衡的划分" class="headerlink" title="平衡的划分"></a>平衡的划分</h3><h2 id="code-1"><a href="#code-1" class="headerlink" title="[code][1]"></a>[code][1]</h2><p>1:  <a href="mailto:git@github.com" target="_blank" rel="noopener">git@github.com</a>:singledo/SortCode.git</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://octopuscloud.top/2019/03/30/七章-快速排序/" data-id="ck471vq1a001f32fzvv91ytpz" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/sort/">sort</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2019/04/14/八章-排序/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          算法导论-第八章
        
      </div>
    </a>
  
  
    <a href="/2019/03/24/六章-堆排序/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">算法导论-第六章(堆排序)</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Categories</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/RFC/">RFC</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/RFC-protocol/">RFC protocol</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ReadNote/">ReadNote</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/linux/">linux</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/protocols/">protocols</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/tools/">tools</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/C/">C</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Data-Struct/">Data Struct</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Ethernet-II/">Ethernet II</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Frame-Format/">Frame Format</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/I2C/">I2C</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/IPv6/">IPv6</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Neighbour-Discover-Protocol/">Neighbour Discover Protocol</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/RFC/">RFC</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/SNMP/">SNMP</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/arthmetic/">arthmetic</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/cgdb/">cgdb</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/chapter-15/">chapter 15</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/data-struct/">data struct</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/deb/">deb</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/defalt-path-for-so-file/">defalt path for so file</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/editer/">editer</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/file-system/">file system</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/gdb-debug/">gdb debug</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/hash/">hash</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux/">linux</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux-driver/">linux driver</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/platform-bus/">platform bus</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/pointer-array/">pointer, array</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/pseudocode/">pseudocode</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/rb-tree/">rb tree</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/sort/">sort</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/ssh-key/">ssh key</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/symbol/">symbol</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/tool/">tool</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/tools/">tools</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/图/">图</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/通信协议/">通信协议</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/C/" style="font-size: 10px;">C</a> <a href="/tags/Data-Struct/" style="font-size: 10px;">Data Struct</a> <a href="/tags/Ethernet-II/" style="font-size: 10px;">Ethernet II</a> <a href="/tags/Frame-Format/" style="font-size: 10px;">Frame Format</a> <a href="/tags/I2C/" style="font-size: 10px;">I2C</a> <a href="/tags/IPv6/" style="font-size: 15px;">IPv6</a> <a href="/tags/Neighbour-Discover-Protocol/" style="font-size: 10px;">Neighbour Discover Protocol</a> <a href="/tags/RFC/" style="font-size: 10px;">RFC</a> <a href="/tags/SNMP/" style="font-size: 10px;">SNMP</a> <a href="/tags/arthmetic/" style="font-size: 10px;">arthmetic</a> <a href="/tags/cgdb/" style="font-size: 10px;">cgdb</a> <a href="/tags/chapter-15/" style="font-size: 10px;">chapter 15</a> <a href="/tags/data-struct/" style="font-size: 15px;">data struct</a> <a href="/tags/deb/" style="font-size: 10px;">deb</a> <a href="/tags/defalt-path-for-so-file/" style="font-size: 10px;">defalt path for so file</a> <a href="/tags/editer/" style="font-size: 10px;">editer</a> <a href="/tags/file-system/" style="font-size: 10px;">file system</a> <a href="/tags/gdb-debug/" style="font-size: 10px;">gdb debug</a> <a href="/tags/hash/" style="font-size: 10px;">hash</a> <a href="/tags/linux/" style="font-size: 20px;">linux</a> <a href="/tags/linux-driver/" style="font-size: 10px;">linux driver</a> <a href="/tags/platform-bus/" style="font-size: 10px;">platform bus</a> <a href="/tags/pointer-array/" style="font-size: 10px;">pointer, array</a> <a href="/tags/pseudocode/" style="font-size: 10px;">pseudocode</a> <a href="/tags/rb-tree/" style="font-size: 10px;">rb tree</a> <a href="/tags/sort/" style="font-size: 20px;">sort</a> <a href="/tags/ssh-key/" style="font-size: 10px;">ssh key</a> <a href="/tags/symbol/" style="font-size: 10px;">symbol</a> <a href="/tags/tool/" style="font-size: 10px;">tool</a> <a href="/tags/tools/" style="font-size: 10px;">tools</a> <a href="/tags/图/" style="font-size: 10px;">图</a> <a href="/tags/通信协议/" style="font-size: 10px;">通信协议</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/12/">December 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/11/">November 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/10/">October 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/09/">September 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/08/">August 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/07/">July 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/06/">June 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/05/">May 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/04/">April 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/03/">March 2019</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2019/12/15/TMUX-使用/">TMUX-使用</a>
          </li>
        
          <li>
            <a href="/2019/11/02/linux-platform-bus-总线分析/platform/">(no title)</a>
          </li>
        
          <li>
            <a href="/2019/11/02/十二章-二叉搜索树/">算法导论-第十二章 二叉查找树</a>
          </li>
        
          <li>
            <a href="/2019/11/02/SegmentationFault-Debug/">(no title)</a>
          </li>
        
          <li>
            <a href="/2019/10/19/linux-platform-bus-总线分析/">linux platform bus 总线分析</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2019 zhangjun<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>



  </div>
</body>
</html>